In recent years, opportunities of distributing digital contents such as documents, image data, and the like via communication lines and large-size recording media such as DVDs and the like are increasing. A digital content delivery service delivers contents to specific users, and is required to have a scheme for preventing contents from leaking except for these users. In content delivery via large-size media, the use of a similar access control mechanism of users has been examined. In this case, encryption, a scramble process, and the like are applied to content data, and a mechanism that allows only authorized users who have authorized key information or know a descramble process to perform a decryption process and to enjoy qualified contents such as documents, image data, and the like is provided.
In such content delivery service, there are content providers who deliver contents. In each content provider, assume that different kinds of access control information must be set for a plurality of contents, and encryption processes using different keys are applied to respective contents, users, user actions (e.g., browse, copy, and the like). In such process, management associated with key information such as key generation, key storage, key delivery, and the like often imposes a heavy load on the content provider. Hence, studies associated with more efficient key management schemes without any security level drop have been made. Some conventional management schemes will be explained below.
<Tree Structure Management Scheme>
The tree structure management scheme is used in an offline content player such as a DVD player or the like, and is suited to invalidate users. In this scheme, key information used in encryption, and an encrypted content are simultaneously delivered or are stored in a medium so that only authorized users can decrypt encrypted data. Key information must be distributed to each user in an appropriate combination, and a huge number of user key information can be efficiently managed by mapping users to a tree structure.
This management scheme has the following three indices upon determining the trade-off of the scheme: 1) the data size of key information to be delivered simultaneously with a content; 2) the data size of key information distributed in advance to each user; and 3) the data size of key information that must be managed by the content provider. An online delivery service attaches importance to 1) that has an influence on the network traffic, but a content provider places top priority on management cost of 3). Note that the weights of the indices vary depending on situations in this way.
As a representative tree structure management scheme, a content delivery model is known (e.g., see “Digital Content Protection Management Scheme” SCIS2001, pp. 213-218). This model uses a tree structure for key derivation, as shown in FIG. 11, and different keys are set in respective nodes (indicated by circles in FIG. 11). Assume that a user key (assume a key held by a player such as a DVD player or the like in the above reference) amounts to an end node (leaf node), and all key data from a root node to an end node are held. This model assumes frequent occurrence of update processes, and the efficiency of key invalidation is improved by this layout.
<Hierarchical Key Management Scheme>
On the other hand, in key management assumed by the hierarchical key management scheme, keys are set in respective nodes as in the above scheme, but keys located at all nodes including the root are distributed to the user (e.g., see C. H. Lin, “Dynamic key management schemes for access control in a hierarchy” Computer Communications, 20:1381-1385, 1997, and J. -C. Birget, X. Zou, G, Noubir, B. Ramamurthy, “Hierarchy-Based Access Control In Distributed Environments” in the Proceedings of IEEE ICC, June 2001).
An access structure shown in FIGS. 12 and 13 is assumed in place of an n-ary tree structure shown in FIG. 11, and locally has a relationship, as shown in FIG. 14. In this case, a structure that can generate a key to be possessed by node n3 from each key in nodes n1 and n2 must be provided separately. According to the reference of Birget et. al. (J. -C. Birget, X. Zou, G, Noubir, B. Ramamurthy, “Hierarchy-Based Access Control In Distributed Environments” in the Proceedings of IEEE ICC, June 2001), the following two schemes are proposed as the scheme for providing this structure.
(1) User Multiple Keying
In this scheme, each node holds a plurality of keys, and a parent node holds all keys of child nodes. FIG. 15 shows an example of the tree structure of this scheme. FIG. 15 shows a set of key data distributed to respective nodes. For example, as can be seen from FIG. 15, a parent node of a node to which {k5} is distributed includes key data k5. Likewise, a parent node includes all key data of child nodes.
(2) One-Way Function Based Keying Schemes
This scheme is designed by expanding the proposal of Lin et. al (C. H. Lin, “Dynamic key management schemes for access control in a hierarchy” Computer Communications, 20:1381-1385, 1997), and can reduce the number of pieces of key information to be held by respective nodes using a one-way hash function. However, in order to generate key data of a child node based on those of a plurality of parent nodes, as shown in FIG. 14, the following manipulation is required. This manipulation will be explained below using FIG. 16. FIG. 16 is a view for explaining a process for generating key data of a child node in the One-way function based keying schemes. In FIG. 16, in order to generate k3 from key data k1 or k2, the following arithmetic operations are made:k3:=F(k1,n3)XOR r13k3:=F(k2,n3)XOR r23where XOR is an exclusive OR of each bit. F( ) is a one-way hash function, which will be described in detail later. n3 is an identifier of a node associated with key data k3, and r13 and r23 are respectively random data associated by node n1 (key data k1) and node n3, and that associated by node n2 (key data k2) and node n3. Both these random data are open to the public.
The function F( ) is configured by F(k_i, n_j)=g^{k_i+n_j} mod p (where p is a prime number, and g is a primitive element), and r13 and r23 above are generated to satisfy F(k1, n3) XOR r13=F(k2, n3) XOR r23.
<Multiple Digest Key Derivation Method>
In 1) User multiple keying of the aforementioned hierarchical key management schemes, respective nodes must have many keys, and the depth of key data to be held increases in proportion to the total number of nodes as the number of layers increases. In 2) One-way function based keying schemes, the key data size to be held by respective nodes is reduced using the one-way hash function. However, public random data such as r13, r23, and the like must be separately held, and the number of data to be held increases as the number of layers increases as in 1).
Furthermore, in 2), the one-way hash function uses exponential operations. The configuration using a trap-door hash function may be used. However, in either case, arithmetic operations that require exponential operations are included, and the calculation cost is huge. Especially, in a device with small arithmetic resources such as a PDA or the like, key calculations require much time and, as a result, interactive processes may be disturbed upon data decryption. A key derivation scheme which can solve these problems and has a similar access structure with a smaller calculation volume is the multiple digest key derivation method.
<Overview of Key Generation>
Generation of node keys of respective nodes in the multiple digest key derivation method is as follows. Assume that an access structure which is to undergo key management is expressed by a directed graph in which the hierarchical relationship has neither loops nor cycles, as shown in FIG. 2. FIG. 2 shows the access structure in the multiple digest key derivation method.
<Division of Nodes>
In order to generate key data, nodes are divided in given key derivation graph G to satisfy the following conditions. Note that the following notation is used: Node(G) is a set of all nodes, N is the number of subsets, and SubG_1, SubG_2, . . . , SubG_N are divided subsets.                SubG_1 ∪ SubG_2 ∪ . . . ∪ SubG_N=Node(G), i.e., all subsets cover all nodes.        Two arbitrary, different nodes n_a and n_b included in SubG_i satisfy n_a<n_b or n_a>n_b. That is, n_a and n_b have a descendant relationship: one node is inevitably a descendant of the other node.        
The number N of divided subsets is called a key derivation order of key derivation graph G, which is represented by Ord(G).
<Node Key Assignment>
One initial key K_1 is calculated for each subset SubG_i, and is assigned as a node key of a root node. To descendant nodes under the root node, node keys are assigned using the following rules.
1) Respective nodes are given numbers associated with N initial keys K_i (1≦i≦N). This number indicates the number of times of execution of the one-way function to each initial key K_i, and “N” that means “none” may be given. If the number of initial key K_i is “N”, this means that a node does not possess any key associated with initial key K_i.
2) Nodes included in each SubG_i are sorted in each set in descending order in accordance with the descendant relationship on the directed graph, and numbers which are incremented by 1 in turn from zero are assigned. This number is associated with initial key K_i.
3) The number associated with initial key K_j (i≠j) of a node included in SubG_i is set to be N (none) if that node is not an ancestor node of a node included in SubG_j (as a subset for initial key K_j), and the number of a node as the ancestor node is set to be the minimum value of numbers assigned to nodes included in SubG_j as descendant nodes.
FIG. 4 is a flowchart of the node key assignment process. Assume that a set of all nodes have already been divided into subsets {SubG_i} (1≦i≦N) which are relatively prime and are not empty, and initial keys K_i for these subsets have been calculated. Let #N(i) be the number of nodes included in subset SubG_i. Also, nodes included in subset SubG_i are sorted in descending order according to the descendant relationship on the directed graph, and are described by SubG_i={n(i, 1), n(i, 2), . . . , n(i, #N(i))}. A node key for node (i, j) is generated by applying the one-way hash function to initial key K_k (1≦k≦N) a prescribed number of times, which is represented by h(i, j, k).
Step S1101 is a loop of variable i which varies from 1 to N, step S1102 is a loop of variable j which varies from 1 to N, and step S1103 is a loop of variable k which varies from 1 to N. It is evaluated in step S1104 if variable i is equal to variable k. If the two variables are equal to each other, the flow advances to step S1105; otherwise, the flow advances to step S1106. In step S1105, “j−1” is substituted in h(i, j, k), and the flow returns to the loop process.
It is evaluated in step S1106 if m which satisfies n(k, m)<n(i, j), i.e., that n(i, j) is an ancestor node of n(k, m) exists. If no m exists, the flow advances to step S1107; otherwise, the flow advances to step S1108. In step S1107, “N” is substituted in h(i, j, k), and the flow returns to the loop process.
In step S1108, min{h(k, m, k)|n(k, m)<n(i, j)}, i.e., a minimum value of h(k, m, k) of nodes n(k, m) whose ancestor node is n(i, j), is substituted in h(i, j, k), and the flow returns to the loop process.
This key generation scheme is configured to satisfy the following two requirements.                Generability: A target node can generate a key of its grandchild node.        Collusion attack avoidability: Even when entities located at two or more arbitrary nodes collude, a key of an ancestor node located at a higher level than each node cannot be generated (unless the one-way function is vulnerable to such attack).        
Under these conditions, the hierarchical key management scheme that can securely perform key generation and key derivation can be implemented. For example, node keys shown in FIG. 3 are generated for the directed graph shown in FIG. 2. FIG. 3 shows node keys for the directed graph in FIG. 2 when the hierarchical key management scheme is applied.
A vector of each node in FIG. 3 expresses the number of times of the hash function to be applied to three initial keys x, y, and z. For example, a cell with a description [2, 2, N] holds H(H(x)) and H(H(y)) as node keys. N means “none”, i.e., no information associated with initial key z. When a hash operation is applied n times in the following description, such process is abbreviated to H^n( ). Based on this notation, a cell with a description [2, 2, N] has two node keys H^2(x) and H^2(y).
<Key Derivation>
A key derivation method to respective nodes by a root key deriver (entity of a root node) and a key derivation method to lower nodes by entities which hold individual keys other than the root key deriver will be explained respectively. The root key deriver randomly and securely generates parameters {x_i} (1≦i≦Ord(G)) as many as key derivation order Ord(G) which is determined according to key derivation graph G, and holds them as individual keys of itself. Furthermore, a plurality of keys are set in respective nodes by the aforementioned key generation sequence. The root key deriver securely distributes keys of respective nodes to entities located at respective nodes. Also, the root key deriver discloses a key derivation graph, and distributes data that can identify the relationship between the distributed keys and their positions on the graph to the entities.
The multiple digest key derivation method can derive a key derivation method to the access structure expressed by an arbitrary directed graph, but the size of each node key depends on the directed graph. More specifically, as is known, the maximum value of a node set having no hierarchical relationship (such set is called an “isolated creek”) matches the size of a node key of a root node.
This means that the communication size required for key derivation becomes inefficient depending on the structure of the directed graph. The directed graph shown in FIG. 5 is such an example. FIG. 5 shows an example of the directed graph in which the maximum value of a node set having no hierarchical relationship matches the size of a node key of a root node.
Since seven nodes n_4 to n_7 of 10 nodes n_i (1≦i≦10) form a node set (=isolated creek) having no hierarchical relationship, a root node must hold seven initial keys. On the other hand, as can be locally seen from a subgraph formed by four nodes n_1, n_2, n_5, and n_6, different keys (a total of three keys) can be distributed from n_1 to n_2, n_5, and n_6, and node keys of descendant nodes suffice to be generated from the node key of n_2. With these examinations, an algorithm that holds seven initial keys is inefficient.